{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Pyramid Transition Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #depth-first-search #breadth-first-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #深度优先搜索 #广度优先搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pyramidTransition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #金字塔转换矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你正在把积木堆成金字塔。每个块都有一个颜色，用一个字母表示。每一行的块比它下面的行 <strong>少一个块</strong> ，并且居中。</p>\n",
    "\n",
    "<p>为了使金字塔美观，只有特定的 <strong>三角形图案</strong> 是允许的。一个三角形的图案由&nbsp;<strong>两个块</strong>&nbsp;和叠在上面的 <strong>单个块</strong> 组成。模式是以三个字母字符串的列表形式&nbsp;<code>allowed</code>&nbsp;给出的，其中模式的前两个字符分别表示左右底部块，第三个字符表示顶部块。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"ABC\"</code>&nbsp;表示一个三角形图案，其中一个 <code>“C”</code> 块堆叠在一个&nbsp;<code>'A'</code>&nbsp;块(左)和一个&nbsp;<code>'B'</code>&nbsp;块(右)之上。请注意，这与 <code>\"BAC\"</code>&nbsp;不同，<code>\"B\"</code>&nbsp;在左下角，<code>\"A\"</code>&nbsp;在右下角。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你从底部的一排积木&nbsp;<code>bottom</code>&nbsp;开始，作为一个单一的字符串，你 <strong>必须</strong> 使用作为金字塔的底部。</p>\n",
    "\n",
    "<p>在给定&nbsp;<code>bottom</code>&nbsp;和&nbsp;<code>allowed</code>&nbsp;的情况下，如果你能一直构建到金字塔顶部，使金字塔中的 <strong>每个三角形图案</strong> 都是允许的，则返回 <code>true</code> ，否则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/08/26/pyramid1-grid.jpg\" style=\"height: 232px; width: 600px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>bottom = \"BCD\", allowed = [\"BCC\",\"CDE\",\"CEA\",\"FFF\"]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>允许的三角形模式显示在右边。\n",
    "从最底层(第3层)开始，我们可以在第2层构建“CE”，然后在第1层构建“E”。\n",
    "金字塔中有三种三角形图案，分别是“BCC”、“CDE”和“CEA”。都是允许的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/08/26/pyramid2-grid.jpg\" style=\"height: 359px; width: 600px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>bottom = \"AAAA\", allowed = [\"AAB\",\"AAC\",\"BCD\",\"BBE\",\"DEF\"]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>允许的三角形模式显示在右边。\n",
    "从最底层(游戏邦注:即第4个关卡)开始，创造第3个关卡有多种方法，但如果尝试所有可能性，你便会在创造第1个关卡前陷入困境。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= bottom.length &lt;= 6</code></li>\n",
    "\t<li><code>0 &lt;= allowed.length &lt;= 216</code></li>\n",
    "\t<li><code>allowed[i].length == 3</code></li>\n",
    "\t<li>所有输入字符串中的字母来自集合&nbsp;<code>{'A', 'B', 'C', 'D', 'E', 'F', 'G'}</code>。</li>\n",
    "\t<li>&nbsp;<code>allowed</code>&nbsp;中所有值都是 <strong>唯一的</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [pyramid-transition-matrix](https://leetcode.cn/problems/pyramid-transition-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [pyramid-transition-matrix](https://leetcode.cn/problems/pyramid-transition-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"BCD\"\\n[\"BCC\",\"CDE\",\"CEA\",\"FFF\"]', '\"AAAA\"\\n[\"AAB\",\"AAC\",\"BCD\",\"BBE\",\"DEF\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        ad = {}\n",
    "        for a in allowed:\n",
    "            if a[0:2] not in ad:\n",
    "                ad[a[0:2]] = [a[-1]]\n",
    "            else:\n",
    "                ad[a[0:2]].append(a[-1])\n",
    "\n",
    "        def bt(bottom, index, nexts):\n",
    "            if len(bottom) == 1:\n",
    "                return True\n",
    "\n",
    "            if index == len(bottom) - 1:\n",
    "                return bt(nexts, 0, \"\")\n",
    "\n",
    "            for i in range(index, len(bottom) - 1):\n",
    "                b = bottom[i : i + 2]\n",
    "                if b not in ad:\n",
    "                    return False\n",
    "                for c in ad[b]:\n",
    "                    if nexts and nexts[-1] + c not in ad:\n",
    "                        continue\n",
    "                    if bt(bottom, index + 1, nexts + c):\n",
    "                        return True\n",
    "                return False\n",
    "            return False\n",
    "\n",
    "        return bt(bottom, 0, \"\")\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    pass\n",
    "    # assert not Solution().pyramidTransition(\n",
    "    #     \"DAAAAD\",\n",
    "    #     [\n",
    "    #         \"DAD\",\n",
    "    #         \"DAE\",\n",
    "    #         \"DAB\",\n",
    "    #         \"DAF\",\n",
    "    #         \"DAC\",\n",
    "    #         \"EAD\",\n",
    "    #         \"EAE\",\n",
    "    #         \"EAB\",\n",
    "    #         \"EAF\",\n",
    "    #         \"EAC\",\n",
    "    #         \"BAD\",\n",
    "    #         \"BAE\",\n",
    "    #         \"BAB\",\n",
    "    #         \"BAF\",\n",
    "    #         \"BAC\",\n",
    "    #         \"FAD\",\n",
    "    #         \"FAE\",\n",
    "    #         \"FAB\",\n",
    "    #         \"FAF\",\n",
    "    #         \"FAC\",\n",
    "    #         \"CAD\",\n",
    "    #         \"CAE\",\n",
    "    #         \"CAB\",\n",
    "    #         \"CAF\",\n",
    "    #         \"CAC\",\n",
    "    #         \"ADD\",\n",
    "    #         \"ADE\",\n",
    "    #         \"ADB\",\n",
    "    #         \"ADF\",\n",
    "    #         \"ADC\",\n",
    "    #         \"AED\",\n",
    "    #         \"AEE\",\n",
    "    #         \"AEB\",\n",
    "    #         \"AEF\",\n",
    "    #         \"AEC\",\n",
    "    #         \"ABD\",\n",
    "    #         \"ABE\",\n",
    "    #         \"ABB\",\n",
    "    #         \"ABF\",\n",
    "    #         \"ABC\",\n",
    "    #         \"AFD\",\n",
    "    #         \"AFE\",\n",
    "    #         \"AFB\",\n",
    "    #         \"AFF\",\n",
    "    #         \"AFC\",\n",
    "    #         \"ACD\",\n",
    "    #         \"ACE\",\n",
    "    #         \"ACB\",\n",
    "    #         \"ACF\",\n",
    "    #         \"ACC\",\n",
    "    #         \"AAD\",\n",
    "    #         \"AAE\",\n",
    "    #         \"AAB\",\n",
    "    #         \"AAF\",\n",
    "    #         \"AAC\",\n",
    "    #         \"AAA\",\n",
    "    #     ],\n",
    "    # )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        permit=defaultdict(list)\n",
    "        for allow in allowed:\n",
    "            permit[allow[:2]].append(allow[-1])\n",
    "        def dfs(up,down):\n",
    "            if len(up)==1 and len(down)==2:\n",
    "                return True\n",
    "            if len(up)+1==len(down):\n",
    "                return dfs('',up)\n",
    "            i=len(up)\n",
    "            for ch in permit[down[i:i+2]]:\n",
    "                if dfs(up+ch,down):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs('',bottom)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        # 将allowed集合转换为字典便于索引与操作\n",
    "        allow = defaultdict(list)\n",
    "        for item in allowed:\n",
    "            allow[item[:2]].append(item[2])\n",
    "        # 从bottom的第一个元素开始深度遍历\n",
    "        return self.deepFirstSearch(bottom, allow, 0)\n",
    "\n",
    "    def deepFirstSearch(self, bottom: str, allow: defaultdict, index: int) -> bool:\n",
    "        if index == len(bottom) - 1:\n",
    "            # print('索引到达边界，在此层基础上进行循环')\n",
    "            index = 0\n",
    "            bottom = bottom[: -1]\n",
    "        # bottom只剩下一个元素，则深度搜索结束，求解成功\n",
    "        if len(bottom) <= 1:\n",
    "            return True\n",
    "        # bottom某相邻两元素不满足allow的条件，求解失败\n",
    "        if bottom[index: index+2] not in allow.keys():\n",
    "            # print(bottom[index: index+2] + '两元素不满足条件')\n",
    "            return False\n",
    "        for item in allow[bottom[index: index+2]]:\n",
    "            # print('开始进行循环,bottom为{0},item为{1}'.format(bottom, item))\n",
    "            _bottom = bottom[: index] + item + bottom[index+1:]\n",
    "            # print('改造后，bottom为{0}，继续放入循环'.format(_bottom))\n",
    "            if self.deepFirstSearch(_bottom, allow, index+1):\n",
    "                # print('此次总循环结束，满足条件, bottom为', _bottom)\n",
    "                return True\n",
    "            # print('不满足条件,一次循环结束,_bottom为{0},item为{1}'.format(_bottom, item))\n",
    "        # print('此次总循环结束，bottom中存在不满足条件, bottom为', bottom)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        m = defaultdict(list)\n",
    "        for allow in allowed:\n",
    "            m[allow[:2]].append(allow[2])\n",
    "        def helper(s):\n",
    "            p = []\n",
    "            for i in range(1, len(s)):\n",
    "                chs = m[s[i - 1] + s[i]]\n",
    "                if len(chs) == 0: return False\n",
    "                p.append(chs)\n",
    "            if len(p) == 1: return True\n",
    "            for chs in product(*p):\n",
    "                if helper(\"\".join(chs)):\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "        return helper(bottom)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\r\n",
    "class Solution:\r\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\r\n",
    "        allow={}\r\n",
    "        for a in allowed:\r\n",
    "            allow.setdefault(a[:2],[]).append(a[2])\r\n",
    "        \r\n",
    "        # @lru_cache\r\n",
    "        def dfs(bottom,idx:int,nxt):\r\n",
    "            if len(nxt)==len(bottom)-1:\r\n",
    "                if len(nxt)==1:\r\n",
    "                    return True\r\n",
    "                return dfs(nxt,0,[])\r\n",
    "\r\n",
    "            base=''.join(bottom[idx:idx+2])\r\n",
    "            if base not in allow:\r\n",
    "                return False\r\n",
    "            for top in allow[base]:\r\n",
    "                nxt.append(top)\r\n",
    "                if dfs(bottom,idx+1,nxt):\r\n",
    "                    return True\r\n",
    "                nxt.pop()\r\n",
    "            return False\r\n",
    "        return dfs(bottom,0,[])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom, allowed):\n",
    "        m = collections.defaultdict(list)\n",
    "        for triples in allowed:\n",
    "            m[triples[:2]].append(triples[-1])\n",
    "        return self.helper(bottom, \"\", m)\n",
    "        \n",
    "    def helper(self, curr, above, m):\n",
    "        if len(curr) == 2 and len(above) == 1:\n",
    "            return True\n",
    "        if len(above) == len(curr) - 1:\n",
    "            return self.helper(above, \"\", m)\n",
    "        pos = len(above)\n",
    "        base = curr[pos : pos+2]\n",
    "        if base in m:\n",
    "            for ch in m[base]:\n",
    "                if self.helper(curr, above + ch, m):\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        n = len(bottom)\n",
    "        rec = defaultdict(set)\n",
    "        for w in allowed:\n",
    "            rec[w[0:2]].add(w[2])\n",
    "        \n",
    "        def dfs(pre, cur):\n",
    "            if len(pre) == 1:\n",
    "                return True\n",
    "            if len(pre) - len(cur) == 1:\n",
    "                return dfs(cur, '')\n",
    "            k = ''\n",
    "            k += pre[len(cur)] + pre[len(cur) + 1]\n",
    "            if k in rec:\n",
    "                for c in rec[k]:\n",
    "                    if dfs(pre, cur + c):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(bottom, '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        m = defaultdict(list)\n",
    "        for allow in allowed:\n",
    "            m[allow[:2]].append(allow[2])\n",
    "        def helper(s):\n",
    "            p = []\n",
    "            for i in range(1, len(s)):\n",
    "                chs = m[s[i - 1] + s[i]]\n",
    "                if len(chs) == 0: return False\n",
    "                p.append(chs)\n",
    "            if len(p) == 1: return True\n",
    "            for chs in product(*p):\n",
    "                if helper(\"\".join(chs)):\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "        return helper(bottom)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\r\n",
    "class Solution:\r\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\r\n",
    "        allow={}\r\n",
    "        for a in allowed:\r\n",
    "            allow.setdefault(a[:2],[]).append(a[2])\r\n",
    "        \r\n",
    "        @lru_cache\r\n",
    "        def dfs(a,b):\r\n",
    "            if len(b)>=2:\r\n",
    "                if not dfs(b,''):\r\n",
    "                    return False\r\n",
    "            if len(a)==2:\r\n",
    "                if not b:\r\n",
    "                    return a in allow\r\n",
    "                else:\r\n",
    "                    return any(dfs(b+t,'') for t in allow.get(a[:2],[]))\r\n",
    "            return any(dfs(a[1:],b+t) for t in allow.get(a[:2],[]))\r\n",
    "            \r\n",
    "        return dfs(bottom,'')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        n=len(bottom)\n",
    "        ad=collections.defaultdict(list)\n",
    "        for x in allowed:\n",
    "            ad[x[:2]].append(x[2])\n",
    "        vis=[]\n",
    "        a=list(bottom)\n",
    "        vis.append(a)\n",
    "        n=len(bottom)\n",
    "\n",
    "        for i in range(n-1,0,-1):\n",
    "            vis.append([\"\"]*i)\n",
    "        #print(vis)\n",
    "\n",
    "       \n",
    "        \n",
    "\n",
    "        def dfs(i,l):\n",
    "            \n",
    "            if i==(n-l-1):\n",
    "                i=0\n",
    "                l+=1\n",
    "            if l==(n-1):\n",
    "                return True\n",
    "\n",
    "            tmp=vis[l][i]+vis[l][i+1]\n",
    "            for nex in ad[tmp]:\n",
    "                \n",
    "                if vis[l+1][i]==\"\":\n",
    "                    \n",
    "                    vis[l+1][i]=nex\n",
    "                    if dfs(i+1,l)==True:\n",
    "                        vis[l+1][i]=\"\"\n",
    "                        return True\n",
    "                    vis[l+1][i]=\"\"\n",
    "            return False\n",
    "        \n",
    "        return dfs(0,0)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        def func(s, i, t):\n",
    "            if self.res:\n",
    "                return\n",
    "            if len(s) == 1:\n",
    "                self.res = True\n",
    "                return\n",
    "            if i == len(s)-1:\n",
    "                func(t, 0, '')\n",
    "            else:\n",
    "                for ch in mapp[s[i:i+2]]:\n",
    "                    func(s, i+1, t+ch)\n",
    "        \n",
    "        mapp = collections.defaultdict(set)\n",
    "        for s in allowed:\n",
    "            mapp[s[:2]].add(s[2])\n",
    "        self.res = False\n",
    "        func(bottom, 0, '')\n",
    "        return self.res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.next = [None] * 7\n",
    "\n",
    "def add(root, word):\n",
    "    cur = root\n",
    "    for c in word:\n",
    "        idx = ord(c) - ord('A')\n",
    "        if not cur.next[idx]:\n",
    "            cur.next[idx] = Trie()\n",
    "        cur = cur.next[idx]\n",
    "\n",
    "def search(root, prefix)->Trie:\n",
    "    cur = root\n",
    "    for c in prefix:\n",
    "        idx = ord(c) - ord('A')\n",
    "        if not cur.next[idx]:\n",
    "            return None\n",
    "        cur = cur.next[idx]\n",
    "    return cur\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        root = Trie()\n",
    "        for pat in allowed:\n",
    "            add(root, pat)\n",
    "        \n",
    "        def dfs(cur, idx, gen):\n",
    "            if len(cur) == 1:\n",
    "                return True\n",
    "            if idx == len(cur) - 1:\n",
    "                return dfs(gen, 0, '')\n",
    "            candidate = search(root, cur[idx:idx + 2])\n",
    "            if not candidate:\n",
    "                return False\n",
    "            for i in range(7):\n",
    "                if not candidate.next[i]:\n",
    "                    continue\n",
    "                if len(gen) and not search(root, gen[-1] + chr(ord('A') + i)):\n",
    "                    continue\n",
    "                if dfs(cur, idx + 1, gen + chr(ord('A') + i)):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(bottom, 0, '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.next = [None] * 7\n",
    "\n",
    "def add(root, word):\n",
    "    cur = root\n",
    "    for c in word:\n",
    "        idx = ord(c) - ord('A')\n",
    "        if not cur.next[idx]:\n",
    "            cur.next[idx] = Trie()\n",
    "        cur = cur.next[idx]\n",
    "\n",
    "def search(root, prefix)->Trie:\n",
    "    cur = root\n",
    "    for c in prefix:\n",
    "        idx = ord(c) - ord('A')\n",
    "        if not cur.next[idx]:\n",
    "            return None\n",
    "        cur = cur.next[idx]\n",
    "    return cur\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        root = Trie()\n",
    "        for pat in allowed:\n",
    "            add(root, pat)\n",
    "        \n",
    "        @lru_cache\n",
    "        def dfs(cur, idx, gen):\n",
    "            if len(cur) == 1:\n",
    "                return True\n",
    "            if idx == len(cur) - 1:\n",
    "                return dfs(gen, 0, '')\n",
    "            candidate = search(root, cur[idx:idx + 2])\n",
    "            if not candidate:\n",
    "                return False\n",
    "            for i in range(7):\n",
    "                if not candidate.next[i]:\n",
    "                    continue\n",
    "                if len(gen) and not search(root, gen[-1] + chr(ord('A') + i)):\n",
    "                    continue\n",
    "                if dfs(cur, idx + 1, gen + chr(ord('A') + i)):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(bottom, 0, '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.next = [None] * 7\n",
    "\n",
    "def add(root, word):\n",
    "    cur = root\n",
    "    for c in word:\n",
    "        idx = ord(c) - ord('A')\n",
    "        if not cur.next[idx]:\n",
    "            cur.next[idx] = Trie()\n",
    "        cur = cur.next[idx]\n",
    "\n",
    "def search(root, prefix)->Trie:\n",
    "    cur = root\n",
    "    for c in prefix:\n",
    "        idx = ord(c) - ord('A')\n",
    "        if not cur.next[idx]:\n",
    "            return None\n",
    "        cur = cur.next[idx]\n",
    "    return cur\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        root = Trie()\n",
    "        for pat in allowed:\n",
    "            add(root, pat)\n",
    "        \n",
    "        def dfs(cur, idx, gen):\n",
    "            if len(cur) == 1:\n",
    "                return True\n",
    "            if idx == len(cur) - 1:\n",
    "                return dfs(gen, 0, '')\n",
    "            candidate = search(root, cur[idx:idx + 2])\n",
    "            if not candidate:\n",
    "                return False\n",
    "            for i in range(7):\n",
    "                if not candidate.next[i]:\n",
    "                    continue\n",
    "                if len(gen) and not search(root, gen[-1] + chr(ord('A') + i)):\n",
    "                    continue\n",
    "                if dfs(cur, idx + 1, gen + chr(ord('A') + i)):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(bottom, 0, '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        mapping = {}\n",
    "        for pat in allowed:\n",
    "            if pat[:2] not in mapping:\n",
    "                mapping[pat[:2]] = []\n",
    "            mapping[pat[:2]].append(pat[2])\n",
    "        \n",
    "        def build(level):\n",
    "            if len(level) == 1:\n",
    "                return True\n",
    "            \n",
    "            next_level = []\n",
    "            for i in range(len(level) - 1):\n",
    "                if level[i : i + 2] not in mapping:\n",
    "                    return False\n",
    "                next_level.append(mapping[level[i : i + 2]])\n",
    "            \n",
    "            return any(build(next_level) for next_level in generate_combinations(next_level, 0, \"\"))\n",
    "        \n",
    "        def generate_combinations(next_level, idx, current):\n",
    "            if idx == len(next_level):\n",
    "                return [current]\n",
    "            \n",
    "            combinations = []\n",
    "            for block in next_level[idx]:\n",
    "                combinations.extend(generate_combinations(next_level, idx + 1, current + block))\n",
    "            return combinations\n",
    "        \n",
    "        return build(bottom)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        allowed_dict = {}\n",
    "        for a in allowed:\n",
    "            if a[:2] not in allowed_dict:\n",
    "                allowed_dict[a[:2]] = [a[2]]\n",
    "            else:\n",
    "                allowed_dict[a[:2]].append(a[2])\n",
    "\n",
    "        def dfs(level):\n",
    "            if len(level) == 1:\n",
    "                return True\n",
    "            for i in range(len(level)-1):\n",
    "                if level[i:i+2] not in allowed_dict:\n",
    "                    return False\n",
    "            next_level = []\n",
    "            self.build_next_level(level, 0, \"\", next_level, allowed_dict)\n",
    "            for nl in next_level:\n",
    "                if dfs(nl):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return dfs(bottom)\n",
    "\n",
    "    def build_next_level(self, level, idx, nl, next_level, allowed_dict):\n",
    "        if idx == len(level) - 1:\n",
    "            next_level.append(nl)\n",
    "            return\n",
    "        for a in allowed_dict[level[idx:idx+2]]:\n",
    "            self.build_next_level(level, idx+1, nl+a, next_level, allowed_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        self.table={}\n",
    "        self.visited={}\n",
    "        for x in allowed:\n",
    "            ind=x[:2]\n",
    "            if ind in self.table:\n",
    "                self.table[ind].append(x[-1])\n",
    "            else:\n",
    "                self.table[ind]=[x[-1]]\n",
    "        return self.help(bottom)\n",
    "    def help(self,buttom:str):\n",
    "        if len(buttom)==2:\n",
    "            return buttom in self.table\n",
    "        if buttom in self.visited:\n",
    "            return False\n",
    "        self.visited[buttom]=False\n",
    "        n=[]\n",
    "        for i in range(len(buttom)-1):\n",
    "            if buttom[i:i+2] not in self.table:\n",
    "                return False\n",
    "            if n==[]:\n",
    "                n=self.table[buttom[i:i+2]]\n",
    "            else:\n",
    "                temp=[]\n",
    "                for str1 in n:\n",
    "                    for str2 in self.table[buttom[i:i+2]]:\n",
    "                        temp.append(str1+str2)\n",
    "                n=temp\n",
    "        for s in n:\n",
    "            if self.help(s):\n",
    "                return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        from collections import defaultdict\n",
    "        t_dict = defaultdict(list)\n",
    "        for f in allowed:\n",
    "            t_dict[f[:2]].append(f[2])\n",
    "\n",
    "\n",
    "        from itertools import permutations\n",
    "        def judge(res):\n",
    "            for i in range(len(res)-1):\n",
    "                \n",
    "                f1,f2 = res[i],res[i+1]\n",
    "                #print(f1,f2)\n",
    "                if f1 + f2 in t_dict:\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "            \n",
    "            return True\n",
    "        \n",
    "        def dfs(bottom):\n",
    "            \n",
    "            if len(bottom) == 2  :\n",
    "                #print(bottom)\n",
    "                return bottom in t_dict\n",
    " \n",
    "\n",
    "            ans = False\n",
    "            res = []\n",
    "            for i in range(len(bottom)-1):\n",
    "                res.append(t_dict[bottom[i:i+2]])\n",
    "            \n",
    "            k = len(res)\n",
    "            i = 0\n",
    "            pre = [[]]\n",
    "            cur = []\n",
    "            for i in range(k):\n",
    "                for f1 in pre:\n",
    "                    for f2 in res[i]:\n",
    "                        cur.append(f1 + [f2])\n",
    "                \n",
    "                pre = cur.copy()\n",
    "                cur = []\n",
    "            \n",
    "            #print(pre)\n",
    "\n",
    "            #print(pre)\n",
    "            for f in pre:\n",
    "                \n",
    "                if judge(f):\n",
    "                    bottom = ''.join(f)\n",
    "                    if dfs(bottom):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(bottom)\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "\n",
    "        d = defaultdict(list)\n",
    "        for s in allowed:\n",
    "            d[s[:2]].append(s[2])\n",
    "        \n",
    "        n = len(bottom)\n",
    "        # cur = [[c] for c in bottom]\n",
    "        # for j in range(1, n):\n",
    "        #     next = [[] for _ in range(len(cur) - 1)]\n",
    "        #     #print(cur)\n",
    "        #     #print(next)\n",
    "\n",
    "        #     for i in range(len(cur) - 1):\n",
    "        #         for c1 in cur[i]:\n",
    "        #             for c2 in cur[i+1]:\n",
    "        #                 k = f'{c1}{c2}'\n",
    "        #                 if k in d:\n",
    "        #                     #print(f'{next} {i}')\n",
    "        #                     next[i].extend(d[k])\n",
    "                        \n",
    "        #         if not next[i]:\n",
    "        #             return False\n",
    "        #     print(next)\n",
    "        #     cur = next\n",
    "        # return True\n",
    "\n",
    "        # wrong beacuse the selection is relative, like 'A|BC|C', the 'A|B' is conflict to 'C|C' so it cannot do the combination freely\n",
    "\n",
    "        def comb(arr, idx, cur, result):\n",
    "            #print(f'{arr} {idx} {cur} {result}')\n",
    "            if idx == len(arr):\n",
    "                #print(cur)\n",
    "                result.append(''.join(cur))\n",
    "                return\n",
    "            for w in arr[idx]:\n",
    "                cur.append(w)\n",
    "                comb(arr, idx + 1, cur, result)\n",
    "                cur.pop()\n",
    "\n",
    "            return result\n",
    "        \n",
    "        cur = [bottom]\n",
    "\n",
    "        for j in range(1, n):\n",
    "            next = set()\n",
    "            for line in cur:\n",
    "                \n",
    "                candidate = [[] for _ in range(len(line) - 1)]\n",
    "                for i in range(len(line) - 1):\n",
    "                    k = line[i:i+2]\n",
    "                    if k in d:\n",
    "                        for c in d[k]:\n",
    "                            candidate[i].append(c)\n",
    "                    else:\n",
    "                        candidate.clear()\n",
    "                        break\n",
    "                if candidate:\n",
    "                    next.update(comb(candidate, 0, [], []))\n",
    "            \n",
    "            if next:\n",
    "                cur = next\n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "            # print(cur)\n",
    "        \n",
    "        return True\n",
    "                \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        from collections import defaultdict\n",
    "        from functools import lru_cache\n",
    "        t_dict = defaultdict(list)\n",
    "        for f in allowed:\n",
    "            t_dict[f[:2]].append(f[2])\n",
    "\n",
    "\n",
    "        from itertools import permutations\n",
    "        @lru_cache\n",
    "        def judge(res):\n",
    "            for i in range(len(res)-1):\n",
    "                \n",
    "                f1,f2 = res[i],res[i+1]\n",
    "                #print(f1,f2)\n",
    "                if f1 + f2 in t_dict:\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "            \n",
    "            return True\n",
    "        \n",
    "        @lru_cache\n",
    "        def dfs(bottom):\n",
    "            \n",
    "            if len(bottom) == 2  :\n",
    "                #print(bottom)\n",
    "                return bottom in t_dict\n",
    " \n",
    "\n",
    "            ans = False\n",
    "            res = []\n",
    "            for i in range(len(bottom)-1):\n",
    "                res.append(t_dict[bottom[i:i+2]])\n",
    "            \n",
    "            k = len(res)\n",
    "            i = 0\n",
    "            pre = [[]]\n",
    "            cur = []\n",
    "            for i in range(k):\n",
    "                for f1 in pre:\n",
    "                    for f2 in res[i]:\n",
    "                        cur.append(f1 + [f2])\n",
    "                \n",
    "                pre = cur.copy()\n",
    "                cur = []\n",
    "            \n",
    "            #print(pre)\n",
    "\n",
    "            #print(pre)\n",
    "            for f in pre:\n",
    "                bottom = ''.join(f)\n",
    "                if judge(bottom):\n",
    "                    #bottom = ''.join(f)\n",
    "                    if dfs(bottom):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(bottom)\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "\n",
    "        d = defaultdict(list)\n",
    "        for s in allowed:\n",
    "            d[s[:2]].append(s[2])\n",
    "        \n",
    "        n = len(bottom)\n",
    "        # cur = [[c] for c in bottom]\n",
    "        # for j in range(1, n):\n",
    "        #     next = [[] for _ in range(len(cur) - 1)]\n",
    "        #     #print(cur)\n",
    "        #     #print(next)\n",
    "\n",
    "        #     for i in range(len(cur) - 1):\n",
    "        #         for c1 in cur[i]:\n",
    "        #             for c2 in cur[i+1]:\n",
    "        #                 k = f'{c1}{c2}'\n",
    "        #                 if k in d:\n",
    "        #                     #print(f'{next} {i}')\n",
    "        #                     next[i].extend(d[k])\n",
    "                        \n",
    "        #         if not next[i]:\n",
    "        #             return False\n",
    "        #     print(next)\n",
    "        #     cur = next\n",
    "        # return True\n",
    "\n",
    "        # wrong beacuse the selection is relative, like 'A|BC|C', the 'A|B' is conflict to 'C|C' so it cannot do the combination freely\n",
    "\n",
    "        def comb(arr, idx, cur, result):\n",
    "            #print(f'{arr} {idx} {cur} {result}')\n",
    "            if idx == len(arr):\n",
    "                #print(cur)\n",
    "                result.append(''.join(cur))\n",
    "                return\n",
    "            for w in arr[idx]:\n",
    "                cur.append(w)\n",
    "                comb(arr, idx + 1, cur, result)\n",
    "                cur.pop()\n",
    "\n",
    "            return result\n",
    "        \n",
    "        cur = [bottom]\n",
    "\n",
    "        for j in range(1, n):\n",
    "            next = set()\n",
    "            for line in cur:\n",
    "                \n",
    "                candidate = [[] for _ in range(len(line) - 1)]\n",
    "                for i in range(len(line) - 1):\n",
    "                    k = line[i:i+2]\n",
    "                    if k in d:\n",
    "                        for c in d[k]:\n",
    "                            candidate[i].append(c)\n",
    "                    else:\n",
    "                        candidate.clear()\n",
    "                        break\n",
    "                if candidate:\n",
    "                    next.update(comb(candidate, 0, [], []))\n",
    "            \n",
    "            if next:\n",
    "                cur = next\n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "            # print(cur)\n",
    "        \n",
    "        return True\n",
    "                \n",
    "\n",
    "        # from ans, yield + back trace to make the solution more concise"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        trans = {}\n",
    "        for p in allowed:\n",
    "            trans.setdefault(p[:2], []).append(p[2])\n",
    "\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def search(a, b):\n",
    "            if len(b) >= 2:\n",
    "                if not search(b, ''):\n",
    "                    return False\n",
    "            if len(a) == 2:\n",
    "                if not b:\n",
    "                    return a in trans\n",
    "                else:\n",
    "                    return any(search(b + t, '') for t in trans.get(a, []))\n",
    "            else:\n",
    "                return any(search(a[1:], b + t) for t in trans.get(a[:2], []))\n",
    "        return search(bottom, '')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        trans = {}\n",
    "        for p in allowed:\n",
    "            trans.setdefault(p[:2], []).append(p[2])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def search(a, b):\n",
    "            if len(b) >= 2:\n",
    "                if not search(b, ''):\n",
    "                    return False\n",
    "            if len(a) == 2:\n",
    "                if not b:\n",
    "                    return a in trans\n",
    "                else:\n",
    "                    return any(search(b + t, '') for t in trans.get(a, []))\n",
    "            else:\n",
    "                return any(search(a[1:], b + t) for t in trans.get(a[:2], []))\n",
    "\n",
    "        return search(bottom, '')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        n, s, d = len(bottom), {bottom}, defaultdict(set)\n",
    "        for x in allowed:\n",
    "            d[x[:-1]].add(x[-1])\n",
    "        while s and n > 1:\n",
    "            tmp = set()\n",
    "            for x in s:\n",
    "                tmp |= set(map(''.join, product(*(d[x[i-1] + x[i]] for i in range(1, n)))))\n",
    "            s = tmp\n",
    "            n -= 1\n",
    "        return bool(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        T = collections.defaultdict(set)\n",
    "        for u, v, w in allowed:\n",
    "            T[u, v].add(w)\n",
    "        @cache\n",
    "        def solve(A):\n",
    "            if len(A) == 1: return True\n",
    "            all_res = []\n",
    "            build(A, [], all_res)\n",
    "            return any(solve(cand) for cand in all_res)\n",
    "\n",
    "        def build(A, ans, all_res, i = 0):\n",
    "            if i + 1 == len(A):\n",
    "                all_res.append( \"\".join(ans))\n",
    "            else:\n",
    "                for w in T[A[i], A[i+1]]:\n",
    "                    ans.append(w)\n",
    "                    build(A, ans, all_res, i+1)\n",
    "                    ans.pop()\n",
    "\n",
    "        return solve(bottom)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def pyramidTransition(self, bottom, allowed):\n",
    "        T = collections.defaultdict(set)\n",
    "        for u, v, w in allowed:\n",
    "            T[u, v].add(w)\n",
    "\n",
    "        #Comments can be used to cache intermediate results\n",
    "        #seen = set()\n",
    "        @cache\n",
    "        def solve(A):\n",
    "            if len(A) == 1: return True\n",
    "            #if A in seen: return False\n",
    "            #seen.add(A)\n",
    "            return any(solve(cand) for cand in build(A, []))\n",
    "\n",
    "        def build(A, ans, i = 0):\n",
    "            if i + 1 == len(A):\n",
    "                yield \"\".join(ans)\n",
    "            else:\n",
    "                for w in T[A[i], A[i+1]]:\n",
    "                    ans.append(w)\n",
    "                    for result in build(A, ans, i+1):\n",
    "                        yield result\n",
    "                    ans.pop()\n",
    "\n",
    "        return solve(bottom)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x,y,z in allowed:\n",
    "            g[x,y].add(z)\n",
    "        def path(bottom,ans,i):\n",
    "            if i == len(bottom)-1:\n",
    "                yield ''.join(ans)\n",
    "            else:\n",
    "                for w in g[bottom[i],bottom[i+1]]:\n",
    "                    ans.append(w)\n",
    "                    for res in path(bottom,ans,i+1):\n",
    "                        yield res\n",
    "                    ans.pop()\n",
    "        @cache\n",
    "        def is_valid(bottom):\n",
    "            if len(bottom) == 1:return True\n",
    "            return any(is_valid(new) for new in path(bottom,[],0))\n",
    "        return is_valid(bottom)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        g = defaultdict(set)\n",
    "        for x,y,z in allowed:\n",
    "            g[x,y].add(z)\n",
    "\n",
    "        def path(bottom,ans,i,res_ans):\n",
    "            if i == len(bottom)-1:\n",
    "                return res_ans.append(''.join(ans))\n",
    "            else:\n",
    "                for w in g[bottom[i],bottom[i+1]]:\n",
    "                    ans.append(w)\n",
    "                    path(bottom,ans,i+1,res_ans)\n",
    "                    ans.pop()\n",
    "\n",
    "        @cache\n",
    "        def is_valid(bottom):\n",
    "            if len(bottom) == 1:return True\n",
    "            res_ans = []\n",
    "            path(bottom,[],0,res_ans)\n",
    "            return any(is_valid(new) for new in res_ans)\n",
    "        return is_valid(bottom)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        dic = defaultdict(list)\n",
    "        for allow in allowed:\n",
    "            dic[allow[:2]].append(allow[-1])\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            if len(s) == 1:\n",
    "                return True\n",
    "            #print(s)\n",
    "            p = []\n",
    "            for i in range(len(s)-1):\n",
    "                ch = dic[s[i:i+2]]\n",
    "                if len(ch) == 0:\n",
    "                    return False\n",
    "                p.append(ch)\n",
    "            for ns in product(*p):\n",
    "                if dfs(''.join(ns)):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(bottom)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        m = defaultdict(list)\n",
    "        for allow in allowed:\n",
    "            m[allow[:2]].append(allow[2])\n",
    "        @cache\n",
    "        def f(s):\n",
    "            p = []\n",
    "            for i in range(1, len(s)):\n",
    "                chs = m[s[i - 1] + s[i]]\n",
    "                if len(chs) == 0: return False\n",
    "                p.append(chs)\n",
    "            if len(p) == 1: return True\n",
    "            for chs in product(*p):\n",
    "                if f(\"\".join(chs)):\n",
    "                    return True\n",
    "            return False\n",
    "        return f(bottom)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        akv=collections.defaultdict(list)\n",
    "        for a0,a1,a2 in allowed:\n",
    "            akv[a0+a1].append(a2)\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            #print(s)\n",
    "            if len(s)==1:\n",
    "                return True \n",
    "            if all([s1+s2 in akv for s1,s2 in pairwise(s)]):\n",
    "                next=deque()\n",
    "                for s1,s2 in pairwise(s):\n",
    "                    nl=len(next)\n",
    "                    if nl==0:\n",
    "                        for third in akv[s1+s2]:\n",
    "                            next.append(third)                     \n",
    "                    for _ in range(nl):\n",
    "                        last=next.pop()\n",
    "                        for third in akv[s1+s2]:\n",
    "                            next.appendleft(last+third)\n",
    "               # print(s,next)\n",
    "                for e in next:\n",
    "                    if(dfs(e)):\n",
    "                        return True\n",
    "                        \n",
    "            return False\n",
    "        return dfs(bottom)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        if not bottom:\n",
    "            return True\n",
    "        if not allowed:\n",
    "            return False\n",
    "        def helper(dict):\n",
    "            res=set()\n",
    "            def dfs1(i,dict,path):\n",
    "                n=len(dict)\n",
    "                if i==n:\n",
    "                    res.add(path)\n",
    "                    return\n",
    "                tmp=path\n",
    "                for j in dict[i]:\n",
    "                    path+=j\n",
    "                    dfs1(i+1,dict,path)\n",
    "                    path=tmp\n",
    "            dfs1(0,dict,\"\")\n",
    "            return res\n",
    "        @cache\n",
    "        def dfs(bottom):\n",
    "            n=len(bottom)\n",
    "            if n==2:\n",
    "                for allow in allowed:\n",
    "                    if allow[:2]==bottom:\n",
    "                        return True\n",
    "                return False\n",
    "            path=defaultdict(set)\n",
    "            for i in range(n-1):\n",
    "                sign=bottom[i]+bottom[i+1]\n",
    "                for allow in allowed:\n",
    "                    if allow[:2]==sign:\n",
    "                        path[i].add(allow[2])\n",
    "            new_bottoms=helper(path)\n",
    "            for new_bottom in new_bottoms:\n",
    "                if len(new_bottom)==n-1:\n",
    "                    if dfs(new_bottom):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return dfs(bottom)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        if not bottom:\n",
    "            return True\n",
    "        if not allowed:\n",
    "            return False\n",
    "        def helper(dict):\n",
    "            res=set()\n",
    "            def dfs1(i,dict,path):\n",
    "                n=len(dict)\n",
    "                if i==n:\n",
    "                    res.add(path)\n",
    "                    return\n",
    "                tmp=path\n",
    "                for j in dict[i]:\n",
    "                    path+=j\n",
    "                    dfs1(i+1,dict,path)\n",
    "                    path=tmp\n",
    "            dfs1(0,dict,\"\")\n",
    "            return res\n",
    "        @cache\n",
    "        def dfs(bottom):\n",
    "            n=len(bottom)\n",
    "            if n==2:\n",
    "                for allow in allowed:\n",
    "                    if allow[:2]==bottom:\n",
    "                        return True\n",
    "                return False\n",
    "            path=defaultdict(set)\n",
    "            for i in range(n-1):\n",
    "                sign=bottom[i]+bottom[i+1]\n",
    "                for allow in allowed:\n",
    "                    if allow[:2]==sign:\n",
    "                        path[i].add(allow[2])\n",
    "            new_bottoms=helper(path)\n",
    "            # print(new_bottoms)\n",
    "            for new_bottom in new_bottoms:\n",
    "                if len(new_bottom)==n-1:\n",
    "                    if dfs(new_bottom):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return dfs(bottom)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\r\n",
    "        n = len(bottom)\r\n",
    "        mp = defaultdict(list)\r\n",
    "        for a in allowed:\r\n",
    "            mp[a[:2]].append(a[2])\r\n",
    "        @cache\r\n",
    "        def DFS(x):\r\n",
    "            if len(x) == 1:\r\n",
    "                return True\r\n",
    "            for i in range(len(x) - 1):\r\n",
    "                if x[i:i + 2] not in mp:\r\n",
    "                    return False \r\n",
    "            nxt = []\r\n",
    "            y = []\r\n",
    "            def dfs(i):\r\n",
    "                if i == len(x) - 1:\r\n",
    "                    nxt.append(\"\".join(y))\r\n",
    "                    return \r\n",
    "                for u in mp[x[i: i + 2]]:\r\n",
    "                    y.append(u)\r\n",
    "                    dfs(i + 1) \r\n",
    "                    y.pop()\r\n",
    "            dfs(0)\r\n",
    "            \r\n",
    "            return any(DFS(z) for z in nxt)          \r\n",
    "            \r\n",
    "        return DFS(bottom)\r\n",
    "\r\n",
    "\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.next = [None] * 7\n",
    "\n",
    "def add(root, word):\n",
    "    cur = root\n",
    "    for c in word:\n",
    "        idx = ord(c) - ord('A')\n",
    "        if not cur.next[idx]:\n",
    "            cur.next[idx] = Trie()\n",
    "        cur = cur.next[idx]\n",
    "\n",
    "def search(root, prefix)->Trie:\n",
    "    cur = root\n",
    "    for c in prefix:\n",
    "        idx = ord(c) - ord('A')\n",
    "        if not cur.next[idx]:\n",
    "            return None\n",
    "        cur = cur.next[idx]\n",
    "    return cur\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        root = Trie()\n",
    "        for pat in allowed:\n",
    "            add(root, pat)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(cur, idx, gen):\n",
    "            if len(cur) == 1:\n",
    "                return True\n",
    "            if idx == len(cur) - 1:\n",
    "                return dfs(gen, 0, '')\n",
    "            candidate = search(root, cur[idx:idx + 2])\n",
    "            if not candidate:\n",
    "                return False\n",
    "            for i in range(7):\n",
    "                if not candidate.next[i]:\n",
    "                    continue\n",
    "                if len(gen) and not search(root, gen[-1] + chr(ord('A') + i)):\n",
    "                    continue\n",
    "                if dfs(cur, idx + 1, gen + chr(ord('A') + i)):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(bottom, 0, '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.next = [None] * 7\n",
    "\n",
    "def add(root, word):\n",
    "    cur = root\n",
    "    for c in word:\n",
    "        idx = ord(c) - ord('A')\n",
    "        if not cur.next[idx]:\n",
    "            cur.next[idx] = Trie()\n",
    "        cur = cur.next[idx]\n",
    "\n",
    "def search(root, prefix)->Trie:\n",
    "    cur = root\n",
    "    for c in prefix:\n",
    "        idx = ord(c) - ord('A')\n",
    "        if not cur.next[idx]:\n",
    "            return None\n",
    "        cur = cur.next[idx]\n",
    "    return cur\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        root = Trie()\n",
    "        for pat in allowed:\n",
    "            add(root, pat)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(cur, idx, gen):\n",
    "            if len(cur) == 1:\n",
    "                return True\n",
    "            if idx == len(cur) - 1:\n",
    "                return dfs(gen, 0, '')\n",
    "            candidate = search(root, cur[idx:idx + 2])\n",
    "            if not candidate:\n",
    "                return False\n",
    "            for i in range(7):\n",
    "                if not candidate.next[i]:\n",
    "                    continue\n",
    "                if len(gen) and not search(root, gen[-1] + chr(ord('A') + i)):\n",
    "                    continue\n",
    "                if dfs(cur, idx + 1, gen + chr(ord('A') + i)):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(bottom, 0, '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        trans = {}\n",
    "        for p in allowed:\n",
    "            trans.setdefault(p[:2], []).append(p[2])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def search(a, b):\n",
    "            if len(a) == 2:\n",
    "                if not b:\n",
    "                    return a in trans\n",
    "                else:\n",
    "                    return any(search(b + t, '') for t in trans.get(a, []))\n",
    "            else:\n",
    "                return any(search(a[1:], b + t) for t in trans.get(a[:2], []))\n",
    "        return search(bottom, '')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "\n",
    "        from functools import lru_cache\n",
    "        \n",
    "        trans = {}\n",
    "        for p in allowed:\n",
    "            trans.setdefault(p[:2], []).append(p[2])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def search(a, b):\n",
    "            if len(a) == 2:\n",
    "                if not b:\n",
    "                    return a in trans\n",
    "                else:\n",
    "                    return any(search(b + t, '') for t in trans.get(a, []))\n",
    "            else:\n",
    "                return any(search(a[1:], b + t) for t in trans.get(a[:2], []))\n",
    "\n",
    "        return search(bottom, '')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        @cache\n",
    "        def dfs(s, i):\n",
    "            if len(s) == 1:\n",
    "                return True\n",
    "            if i == len(s) - 1:\n",
    "                return dfs(s[:-1], 0)\n",
    "            return any(dfs(s[:i]+char+s[i+1:], i+1) for char in d[s[i:i+2]])\n",
    "    \n",
    "        d = defaultdict(list)\n",
    "        for al in allowed:\n",
    "            d[al[:2]].append(al[2])\n",
    "        return dfs(bottom, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        trans = defaultdict(list)\n",
    "        for p in allowed:\n",
    "            trans[p[:2]].append(p[2])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def search(a, b):\n",
    "            if len(a) == 2:\n",
    "                if not b:\n",
    "                    return len(trans[a]) > 0\n",
    "                else:\n",
    "                    return any(search(b + t, '') for t in trans[a])\n",
    "            else:\n",
    "                return any(search(a[1:], b + t) for t in trans[a[:2]])\n",
    "\n",
    "        return search(bottom, '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        # 968ms\n",
    "        # allowed = set(allowed)\n",
    "        # @cache\n",
    "        # def dfs(bottom,cur):\n",
    "        #     if len(bottom) == 1:\n",
    "        #         return True\n",
    "        #     if len(cur) == len(bottom) - 1:\n",
    "        #         return dfs(cur,'')\n",
    "        #     for x in ('A', 'B', 'C', 'D', 'E', 'F', 'G'):\n",
    "        #         if bottom[len(cur):len(cur) + 2]  + x in allowed:\n",
    "        #             if dfs(bottom, cur + x):\n",
    "        #                 return True\n",
    "        #     return False\n",
    "\n",
    "        # return dfs(bottom, '')\n",
    "        \n",
    "        d = defaultdict(list)\n",
    "        for x in allowed:\n",
    "            d[x[:2]].append(x[2])\n",
    "\n",
    "        @cache\n",
    "        def dfs(bottom,cur):\n",
    "            if len(bottom) == 2:\n",
    "                if not cur:\n",
    "                    return len(d[bottom]) > 0\n",
    "                else:\n",
    "                    return any(dfs(cur + t,'') for t in d[bottom])\n",
    "            else:\n",
    "                return any(dfs(bottom[1:],cur + t) for t in d[bottom[:2]])\n",
    "        \n",
    "        return dfs(bottom,'')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\r\n",
    "class Solution:\r\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\r\n",
    "        allow={}\r\n",
    "        for a in allowed:\r\n",
    "            allow.setdefault(a[:2],[]).append(a[2])\r\n",
    "        \r\n",
    "        # @lru_cache\r\n",
    "        cache={}\r\n",
    "\r\n",
    "        def dfs(bottom,idx:int,nxt):\r\n",
    "            h=(bottom,idx,''.join(nxt))\r\n",
    "            if h in cache:\r\n",
    "                return cache[h]\r\n",
    "            if len(nxt)==len(bottom)-1:\r\n",
    "                if len(nxt)==1:\r\n",
    "                    return True\r\n",
    "                return dfs(''.join(nxt),0,[])\r\n",
    "\r\n",
    "            base=''.join(bottom[idx:idx+2])\r\n",
    "            if base not in allow:\r\n",
    "                return False\r\n",
    "            for top in allow[base]:\r\n",
    "                nxt.append(top)\r\n",
    "                if dfs(bottom,idx+1,nxt):\r\n",
    "                    return True\r\n",
    "                nxt.pop()\r\n",
    "            cache[h]=False\r\n",
    "            return False\r\n",
    "        return dfs(bottom,0,[])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        n = len(bottom)\n",
    "        rec = defaultdict(set)\n",
    "        for w in allowed:\n",
    "            rec[w[0:2]].add(w[2])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(pre, cur):\n",
    "            if len(pre) == 1:\n",
    "                return True\n",
    "            if len(pre) - len(cur) == 1:\n",
    "                return dfs(cur, '')\n",
    "            k = ''\n",
    "            k += pre[len(cur)] + pre[len(cur) + 1]\n",
    "            if k in rec:\n",
    "                for c in rec[k]:\n",
    "                    if dfs(pre, cur + c):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(bottom, '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        allowed = set(allowed)\n",
    "        @cache\n",
    "        def dfs(bottom,cur):\n",
    "            if len(bottom) == 1:\n",
    "                return True\n",
    "            if len(cur) == len(bottom) - 1:\n",
    "                return dfs(cur,'')\n",
    "            for x in ('A', 'B', 'C', 'D', 'E', 'F', 'G'):\n",
    "                if bottom[len(cur):len(cur) + 2]  + x in allowed:\n",
    "                    if dfs(bottom, cur + x):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return dfs(bottom, '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:\n",
    "        n = len(bottom)\n",
    "        rec = defaultdict(list)\n",
    "        for w in allowed:\n",
    "            rec[w[0:2]].append(w[2])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(pre, cur):\n",
    "            if len(pre) == 1:\n",
    "                return True\n",
    "            if len(pre) - len(cur) == 1:\n",
    "                return dfs(cur, '')\n",
    "            k = ''\n",
    "            k += pre[len(cur)] + pre[len(cur) + 1]\n",
    "            if k in rec:\n",
    "                for c in rec[k]:\n",
    "                    if dfs(pre, cur + c):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(bottom, '')"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
